Monte Carlo : Voyageur du Commerce¶
Modules nécessaires¶
In [2]:
import numpy as np
import pandas as pd
import geopy
import time
from scipy.stats import chisquare
from matplotlib import pyplot as plt
from tsp_solver.greedy import solve_tsp
from bokeh.plotting import figure, show
from bokeh.io import output_notebook, push_notebook, show
%matplotlib inline
Question n°1¶
Création de la loi multinomiale¶
D'abord, il faut une fonction qui choisit une des villes possibles, selon des probabilités choisies en amont. Cela est réalisé grâce à une loi uniforme sur $[0;1]$ et à une segmentation choisie sur $[0;1]$ à partir de la probabilité de choisir une ville.
In [2]:
def assign(M,suplimits,rand):
"""
suplimits : Liste des proba cumulées
rand : Liste des probabilités uniformes sur [0;1]
M : Nombres de ville
"""
sample = []
for i in range(len(rand)):
if rand[i]<suplimits[0]:
sample.append(1)
for j in range(len(suplimits)):
if rand[i]>= suplimits[j] and rand[i]<=suplimits[j+1]:
sample.append(j+2)
return sample
In [3]:
#Exemple
assign(3,[0.1,0.5,1],np.random.uniform(0,1,10))
Out[3]:
Ensuite, il faut réitérer cette étape plusieurs fois, mais il faut en plus compter dans ce nombre d'itérations le nombre de fois qu'une ville a été sélectionné. Nous prenons le soin de vérifier que les probabilités données en entrée sont bien normées à $1$.
In [4]:
def Nmulti(N,n,proba):
"""
N : Nombre de "dés" multinomiales
n : Nombre de Simulations (nombre de fois qu'on va jeter les N dès)
proba : Les poids attribués à chaque ville ~ les probabilités de tomber dessus
"""
proba_norm = [float(i)/sum(proba) for i in proba]
if abs(1-sum(proba_norm))<=10^-10:
return "Somme de proba différent de 1"
else:
p = proba_norm
suplimits = np.cumsum(p)
matrix = [] #Liste vide où l'on va ajouté des listes
for i in range(1,n+1):
matrix.append(assign(len(proba),suplimits,np.random.uniform(0,1,N)))
res =[]
for i in range(n):
l=[]
for j in range(1,len(proba)+1):
l.append(matrix[i].count(j))
res.append(l)
return np.array(res)
In [5]:
#Exemple
Nmulti(100,10,[1/2,1/4,1/4])
Out[5]:
Génération aléatoires de villes pour le TSP¶
Afin d'éviter de créer $n$ villes manuellement, le programme suivant s'en occupe.
In [19]:
def gen_villes(nb):
x = np.random.uniform(0,1,nb)
y = np.random.uniform(0,1,nb)
villes = []
for i in range(len(x)):
villes.append([str(i+1),(x[i],y[i])])
return(villes)
Ensuite, nous avons deux fonctions pour tracer les villes dans un plan. L'un avec juste le nombre de villes souhaité, l'autre avec déjà une liste de ville établie.
In [20]:
def plot_villes(nb):
villes = gen_villes(nb)
fig = plt.figure()
ax = fig.add_subplot(111)
A = [villes[i][1][0] for i in range(len(villes))]
B = [villes[i][1][1] for i in range(len(villes))]
n=[villes[i][0] for i in range(len(villes))]
for i, txt in enumerate(n):
ax.annotate(txt, (A[i],B[i]))
plt.scatter(A,B)
plt.grid()
plt.axis('equal')
plt.show()
def plot_villes_connus(villes):
fig = plt.figure()
ax = fig.add_subplot(111)
A = [villes[i][1][0] for i in range(len(villes))]
B = [villes[i][1][1] for i in range(len(villes))]
n=[villes[i][0] for i in range(len(villes))]
for i, txt in enumerate(n):
ax.annotate(txt, (A[i],B[i]))
plt.scatter(A,B)
plt.grid()
plt.axis('equal')
plt.show()
In [21]:
villes = gen_villes(10)
plot_villes_connus(villes)
L'algorithme générant une matrice de distances à partir de coordonnées est le suivant :
In [22]:
def matrice_distances(villes):
matrice_des_distances = [[0 for i in range(len(villes))]for j in range(0,len(villes))]
for i in range(0,len(villes)):
for j in range(0,len(villes)):
matrice_des_distances[i][j]=np.sqrt(((villes[i][1][0]-villes[j][1][0])**2) + ((villes[i][1][1]-villes[j][1][1])**2))
return(matrice_des_distances)
Par rapport à notre exemple :
In [23]:
matrice_distance = matrice_distances(villes)
pd.DataFrame(matrice_distance ,
columns = range(1,len(matrice_distance)+1),
index = range(1,len(matrice_distance )+1))
Out[23]:
Solving the TSP¶
Cet algorithme génére une matrice de probabilité finale à partir d'une matrice de probabilité initiale. Il s'agit de la chaîne de Markov optimale pour effectuer le trajet en une distance minimale.
In [24]:
def traveling_salesman_problem_CE_algorithm(matrice_des_distances,matrice_proba_init,nb_simulations, pourcentage_meilleurs_scores):
res = []
score = []
meilleurs_scores = []
réccurence = {}
matrice_proba_finale = []
for j in range(0,nb_simulations):
matrice_proba = [[None]*len(matrice_proba_init) for _ in range(len(matrice_proba_init))]
for k in range(len(matrice_proba_init)):
for l in range(len(matrice_proba_init)):
matrice_proba[k][l]=matrice_proba_init[k][l]
scénario = []
for k in range(0,len(matrice_des_distances)-1):
scénario.append(Nmulti(1,1,[matrice_proba[k][i] for i in range(0,len(matrice_des_distances))]).argmax())
for l in range(k+1,len(matrice_des_distances)):
matrice_proba[l][scénario[k]]=0
s = sum(matrice_proba[k+1][i] for i in range(0,len(matrice_des_distances)))
for p in range(0,len(matrice_des_distances)):
matrice_proba[k+1][p]*=1/s
scénario.append(Nmulti(1,1,[matrice_proba[-1][i] for i in range(0,len(matrice_des_distances))]).argmax())
res.append(scénario)
for i in range(len(res)):
score.append((sum(matrice_des_distances[res[i][j]][res[i][j+1]] for j in range(0,len(matrice_des_distances)-1)),res[i]))
score.sort()
meilleurs_scores=score[:int(nb_simulations*pourcentage_meilleurs_scores)]
for f in range(0,len(matrice_des_distances)):
for g in range(0,len(matrice_des_distances)):
réccurence[(f,g)]=0
for h in range(len(meilleurs_scores)):
for j in range(0,len(matrice_des_distances)):
for k in range(0,len(matrice_des_distances)):
if meilleurs_scores[h][1][j]==k:
réccurence[(j,k)]+=1
matrice_proba_finale = [[None]*len(matrice_proba_init) for _ in range(len(matrice_proba_init))]
for i in range(0,len(matrice_des_distances)):
for j in range(0,len(matrice_des_distances)):
if réccurence[(i,j)]/(nb_simulations*pourcentage_meilleurs_scores)<0.05:
matrice_proba_finale[i][j] = 0.0001
elif réccurence[(i,j)]/(nb_simulations*pourcentage_meilleurs_scores)>0.95:
matrice_proba_finale[i][j] = 0.9999
else:
matrice_proba_finale[i][j] = réccurence[(i,j)]/(nb_simulations*pourcentage_meilleurs_scores)
for i in range(len(matrice_proba_finale)):
matrice_proba_finale[i] = [float(j)/sum(matrice_proba_finale[i]) for j in matrice_proba_finale[i]]
return(matrice_proba_finale)
In [25]:
m = matrice_distances(villes)
matrice_proba_init=[[1/len(m) for i in range(0,len(m))] for j in range(0,len(m))]
start_time = time.time()
print(traveling_salesman_problem_CE_algorithm(m,matrice_proba_init,10000,0.05))
print("--- %s seconds ---" % (time.time() - start_time))
Exemple:
In [26]:
matrice_proba_init = [[1/len(matrice_distance) for i in range(0,len(matrice_distance))] for j in range(0,len(matrice_distance))]
df = traveling_salesman_problem_CE_algorithm(matrice_distance,
matrice_proba_init,
1000,
0.05)
pd.DataFrame(df,
columns = range(1,len(df)+1),
index = range(1,len(df)+1))
Out[26]:
In [27]:
def solution_traveling_salesman_problem(villes):
matrice_des_distances = matrice_distances(villes)
matrice_proba_init=[[1/len(matrice_des_distances) for i in range(0,len(matrice_des_distances))] for j in range(0,len(matrice_des_distances))]
list_mat=[]
list_mat.append(matrice_proba_init)
count = 0
while True :
matrice_proba_précisée = traveling_salesman_problem_CE_algorithm(matrice_des_distances,list_mat[-1],10000,0.05)
list_mat.append(matrice_proba_précisée)
s=0
for i in range(len(matrice_proba_précisée)):
for j in range(len(matrice_proba_précisée)):
if list_mat[-1][i][j]>0.99:
s+=1
count = count + 1
if s==len(matrice_proba_précisée) : break
res = []
for i in range(len(matrice_proba_précisée)):
res.append(np.argmax(list_mat[-1][i]))
solution = []
for i in range(0, len(res)):
solution.append(villes[res[i]][0])
distance = sum(matrice_des_distances[res[i]][res[i+1]] for i in range(len(res)-1))
solution.append(distance)
solution.append(count)
return(solution)
In [28]:
start_time = time.time()
S1 = solution_traveling_salesman_problem(villes)
print("--- %s seconds ---" % (time.time() - start_time))
print(S1)
Représentation graphique du chemin :
In [29]:
villes_sorted = []
for i in range(len(S1[:-2])):
villes_sorted.append(villes[int(S1[:-2][i])-1])
fig2 = plt.figure()
ax = fig2.add_subplot(111)
C = [villes_sorted[i][1][0] for i in range(len(villes))]
D = [villes_sorted[i][1][1] for i in range(len(villes))]
n=[villes_sorted[i][0] for i in range(len(villes))]
plt.plot(C,D)
for i, txt in enumerate(n):
ax.annotate(txt, (C[i],D[i]))
plt.axis('equal')
plt.grid()
plt.show()
Solution donnée par le package TSP_Solver¶
Un module python résout le problème.
In [30]:
D = matrice_distances(villes)
start_time = time.time()
path = solve_tsp( D )
print (path)
print("--- %s seconds ---" % (time.time() - start_time))
villes_sorted_pack = []
for i in range(len(path)):
villes_sorted_pack.append(villes[path[i]])
distance = 0
for i in range(0, len(path)-1):
distance += D[path[i]][path[i+1]]
print(distance)
fig3 = plt.figure()
ax = fig3.add_subplot(111)
E = [villes_sorted_pack[i][1][0] for i in range(len(villes_sorted_pack))]
F = [villes_sorted_pack[i][1][1] for i in range(len(villes_sorted_pack))]
n=[villes_sorted_pack[i][0] for i in range(len(villes_sorted_pack))]
plt.plot(E,F)
for i, txt in enumerate(n):
ax.annotate(txt, (E[i],F[i]))
plt.axis('equal')
plt.grid()
plt.show()
In [31]:
def tsp_solver(villes):
D = matrice_distances(villes)
start_time = time.time()
path = solve_tsp(D)
print("--- %s seconds ---" % (time.time() - start_time))
villes_sorted_pack = []
for i in range(len(path)):
villes_sorted_pack.append(villes[path[i]])
distance = 0
for i in range(0, len(path)-1):
distance += D[path[i]][path[i+1]]
fig3 = plt.figure()
ax = fig3.add_subplot(111)
E = [villes_sorted_pack[i][1][0] for i in range(len(villes_sorted_pack))]
F = [villes_sorted_pack[i][1][1] for i in range(len(villes_sorted_pack))]
n=[villes_sorted_pack[i][0] for i in range(len(villes_sorted_pack))]
plt.plot(E,F)
for i, txt in enumerate(n):
ax.annotate(txt, (E[i],F[i]))
plt.axis('equal')
plt.grid()
plt.show()
path = [x+1 for x in path] #car on ne commence à 1 pour le numéro des villes
return distance, path
Tests de vitesse¶
On fait varier le nombre de simulations pour des configurations de 3 Ã 30 villes.
In [ ]:
l_etape = []
l=[]
nb_villes = [i for i in range(3,31)]
nb_simul = [1000,10000,50000]
for i in nb_villes:
villes = gen_villes(i)
S_tsp = tsp_solver(villes)
for j in nb_simul:
start_time = time.time()
S_etape = solution_traveling_salesman_problem(villes,j)
timing_etape = time.time() - start_time
l_etape.append(S_etape[-2])
l_etape.append(timing_etape)
l_etape.append(S_tsp[0])
l.append(l_etape)
l_etape=[]
In [33]:
df = pd.DataFrame(l, index = [i for i in range(3,34)], columns = ["Distance 1 000 simulations","Temps 1 000 simulations","Distance 10 000 simulations","Temps 10 000 simulations","Distance 50 000 simulations","Temps 50 000 simulations","Distance TSP_Solver"])
df.index.names = ['Nombre de villes']
df
Out[33]:
Tracé des graphes avec le module $bokeh$
In [34]:
from bokeh.plotting import figure, show
from bokeh.io import output_notebook, push_notebook, show
p1 = figure(title="1 000 simulations - Temps pour résoudre TSP")
p1.grid.grid_line_alpha=0.3
p1.xaxis.axis_label = 'Nombre de Villes'
p1.yaxis.axis_label = 'Temps en secondes'
p1.line(df.index, df["Temps 1 000 simulations"],color='red')
p2 = figure(title="10 000 simulations - Temps pour résoudre TSP")
p2.grid.grid_line_alpha=0.3
p2.xaxis.axis_label = 'Nombre de Villes'
p2.yaxis.axis_label = 'Temps en secondes'
p2.line(df.index, df["Temps 10 000 simulations"],color='blue')
p3 = figure(title="50 000 simulations - Temps pour résoudre TSP")
p3.grid.grid_line_alpha=0.3
p3.xaxis.axis_label = 'Nombre de Villes'
p3.yaxis.axis_label = 'Temps en secondes'
p3.line(df.index, df["Temps 50 000 simulations"],color='green')
p4 = figure(title="1 000, 10 000 et 50 000 simulations - Temps pour résoudre TSP")
p4.grid.grid_line_alpha=0.3
p4.xaxis.axis_label = 'Nombre de Villes'
p4.yaxis.axis_label = 'Temps en secondes'
p4.line(df.index, df["Temps 1 000 simulations"], color='red', legend='1 000 simulations')
p4.line(df.index, df["Temps 10 000 simulations"], color='blue', legend='10 000 simulations')
p4.line(df.index, df["Temps 50 000 simulations"], color='green', legend='50 000 simulations')
p4.legend.location = "top_left"
window_size = 30
window = np.ones(window_size)/float(window_size)
show(p1)
show(p2)
show(p3)
show(p4)
output_notebook()
In [35]:
p5 = figure(title="1 000 simulations - Pourcentage d'écartement par rapport à TSP_Solver")
p5.grid.grid_line_alpha=0.3
p5.xaxis.axis_label = 'Nombre de Villes'
p5.yaxis.axis_label = 'Ecart en pourcentage'
p5.line(df.index, abs((df["Distance 1 000 simulations"]-df["Distance TSP_Solver"])/df["Distance TSP_Solver"]), color ="red")
p6 = figure(title="10 000 simulations - Pourcentage d'écartement par rapport à TSP_Solver")
p6.grid.grid_line_alpha=0.3
p6.xaxis.axis_label = 'Nombre de Villes'
p6.yaxis.axis_label = 'Ecart en pourcentage'
p6.line(df.index, abs((df["Distance 10 000 simulations"]-df["Distance TSP_Solver"])/df["Distance TSP_Solver"]), color ="blue")
p7 = figure(title="50 000 simulations - Pourcentage d'écartement par rapport à TSP_Solver")
p7.grid.grid_line_alpha=0.3
p7.xaxis.axis_label = 'Nombre de Villes'
p7.yaxis.axis_label = 'Ecart en pourcentage'
p7.line(df.index, abs((df["Distance 50 000 simulations"]-df["Distance TSP_Solver"])/df["Distance TSP_Solver"]), color ="green")
p8 = figure(title="1 000, 10 000 et 50 000 simulations - Pourcentage d'écartement par rapport à TSP_Solver")
p8.grid.grid_line_alpha=0.3
p8.xaxis.axis_label = 'Nombre de Villes'
p8.yaxis.axis_label = 'Ecart en pourcentage'
p8.line(df.index, abs((df["Distance 1 000 simulations"]-df["Distance TSP_Solver"])/df["Distance TSP_Solver"]),
color='red', legend='1 000 simulations')
p8.line(df.index, abs((df["Distance 10 000 simulations"]-df["Distance TSP_Solver"])/df["Distance TSP_Solver"]),
color='blue', legend='10 000 simulations')
p8.line(df.index, abs((df["Distance 50 000 simulations"]-df["Distance TSP_Solver"])/df["Distance TSP_Solver"]),
color='green', legend='50 000 simulations')
p8.legend.location = "top_left"
window_size = 400
window = np.ones(window_size)/float(window_size)
show(p5)
show(p6)
show(p7)
show(p8)
output_notebook()
Loi de Dirichlet¶
Il s'agit désormais d'implémenter l'algorithme trouvant la solution du TSP en rajoutant une loi du Dirichlet.
In [36]:
np.random.dirichlet([100,100,100],1)
Out[36]:
In [37]:
def traveling_salesman_problem_CE_algorithm_dirichlet(matrice_des_distances,matrice_poids_init,nb_simulations, pourcentage_meilleurs_scores):
res = []
score = []
meilleurs_scores = []
réccurence = {}
matrice_poids_finale = []
matrice_proba_init = [np.random.dirichlet(matrice_poids_init[k],1)[0] for k in range(len(matrice_poids_init))]
for i in range(len(matrice_proba_init)):
for j in range(len(matrice_proba_init)):
if matrice_proba_init[i][j]==0:
matrice_proba_init[i][j] = 0.0001
for i in range(len(matrice_proba_init)):
matrice_proba_init[i] = [float(j)/sum(matrice_proba_init[i]) for j in matrice_proba_init[i]]
for j in range(0,nb_simulations):
matrice_proba = [[None]*len(matrice_proba_init) for _ in range(len(matrice_proba_init))]
for k in range(len(matrice_proba_init)):
for l in range(len(matrice_proba_init)):
matrice_proba[k][l]=matrice_proba_init[k][l]
scénario = []
for k in range(0,len(matrice_proba)-1):
scénario.append(Nmulti(1,1,matrice_proba[k]).argmax())
for l in range(k+1,len(matrice_proba)):
matrice_proba[l][scénario[k]]=0
s = sum(matrice_proba[k+1][i] for i in range(0,len(matrice_proba)))
for p in range(0,len(matrice_proba)):
matrice_proba[k+1][p]*=1/s
scénario.append(Nmulti(1,1,matrice_proba[-1]).argmax())
res.append(scénario)
for i in range(len(res)):
score.append((sum(matrice_des_distances[res[i][j]][res[i][j+1]] for j in range(0,len(matrice_des_distances)-1)),res[i]))
score.sort()
meilleurs_scores=score[:int(nb_simulations*pourcentage_meilleurs_scores)]
for f in range(0,len(matrice_des_distances)):
for g in range(0,len(matrice_des_distances)):
réccurence[(f,g)]=0
for h in range(len(meilleurs_scores)):
for j in range(0,len(matrice_des_distances)):
for k in range(0,len(matrice_des_distances)):
if meilleurs_scores[h][1][j]==k:
réccurence[(j,k)]+=1
matrice_poids_finale = [[None]*len(matrice_poids_init) for _ in range(len(matrice_poids_init))]
for i in range(0,len(matrice_des_distances)):
for j in range(0,len(matrice_des_distances)):
matrice_poids_finale[i][j]=100*réccurence[(i,j)]#matrice_poids_init[i][j]*réccurence[(i,j)]
return(matrice_poids_finale)
In [38]:
def solution_traveling_salesman_problem_dirichlet(villes,nb_simul):
matrice_des_distances = matrice_distances(villes)
matrice_poids_init=[[100]*len(matrice_des_distances) for _ in range(len(matrice_des_distances))]
list_mat=[]
list_mat.append(matrice_poids_init)
list_mat_proba = []
count = 0
while True :
matrice_poids_précisée = traveling_salesman_problem_CE_algorithm_dirichlet(matrice_des_distances,list_mat[-1],nb_simul,0.05)
list_mat.append(matrice_poids_précisée)
matrice_proba_correspondante = [np.random.dirichlet(matrice_poids_précisée[k],1)[0] for k in range(len(matrice_poids_précisée))]
list_mat_proba.append(matrice_proba_correspondante)
s=0
for i in range(len(matrice_proba_correspondante)):
for j in range(len(matrice_proba_correspondante)):
if list_mat[-1][i][j]>0.99:
s+=1
count = count + 1
if s==len(matrice_proba_correspondante) : break
res = []
for i in range(len(list_mat_proba[-1])):
res.append(np.argmax(list_mat_proba[-1][i]))
solution = []
for i in range(0, len(res)):
solution.append(villes[res[i]][0])
distance = sum(matrice_des_distances[res[i]][res[i+1]] for i in range(len(res)-1))
solution.append(distance)
solution.append(count)
return(solution)
In [40]:
start_time = time.time()
S2 = solution_traveling_salesman_problem_dirichlet(villes,10000)
print(S2)
print("--- %s seconds ---" % (time.time() - start_time))
In [41]:
villes_sorted = []
for i in range(len(S2[:-1])):
villes_sorted.append(villes[int(S2[:-1][i])-1])
fig2 = plt.figure()
ax = fig2.add_subplot(111)
G = [villes_sorted[i][1][0] for i in range(len(villes))]
H = [villes_sorted[i][1][1] for i in range(len(villes))]
n=[villes_sorted[i][0] for i in range(len(villes))]
plt.plot(G,H)
for i, txt in enumerate(n):
ax.annotate(txt, (G[i],H[i]))
plt.axis('equal')
plt.grid()
plt.show()
Tests de vitesse¶
On fait varier le nombre de simulations pour des configurations de 3 Ã 30 villes.
In [25]:
l_etape = []
l=[]
nb_villes = [i for i in range(3,31)]
nb_simul = [1000,10000,50000]
for i in nb_villes:
villes = gen_villes(i)
S_tsp = tsp_solver(villes)
for j in nb_simul:
start_time = time.time()
S_etape = solution_traveling_salesman_problem_dirichlet(villes,j)
timing_etape = time.time() - start_time
l_etape.append(S_etape[-2])
l_etape.append(timing_etape)
l_etape.append(S_tsp[0])
l.append(l_etape)
l_etape=[]
In [26]:
dfD = pd.DataFrame(l, index = [i for i in range(3,31)], columns = ["Distance 1 000 simulations","Temps 1 000 simulations","Distance 10 000 simulations","Temps 10 000 simulations","Distance 50 000 simulations","Temps 50 000 simulations","Distance TSP_Solver"])
dfD.index.names = ['Nombre de villes']
dfD
Out[26]:
In [42]:
dfD = pd.read_csv('Liste2.txt', sep="\t")
dfD = dfD.drop(['Unnamed: 0','Unnamed: 8', 'Unnamed: 9', 'Unnamed: 10', 'Unnamed: 11', "Unnamed: 12", "Unnamed: 13","Unnamed: 14"], axis=1)
dfD
Out[42]:
In [43]:
output_notebook()
p1 = figure(title="1 000 simulations - Temps pour résoudre TSP")
p1.grid.grid_line_alpha=0.3
p1.xaxis.axis_label = 'Nombre de Villes'
p1.yaxis.axis_label = 'Temps en secondes'
p1.line(dfD.index, dfD["Temps 1 000 simulations"],color='red')
p2 = figure(title="10 000 simulations - Temps pour résoudre TSP")
p2.grid.grid_line_alpha=0.3
p2.xaxis.axis_label = 'Nombre de Villes'
p2.yaxis.axis_label = 'Temps en secondes'
p2.line(dfD.index, dfD["Temps 10 000 simulations"],color='blue')
p3 = figure(title="50 000 simulations - Temps pour résoudre TSP")
p3.grid.grid_line_alpha=0.3
p3.xaxis.axis_label = 'Nombre de Villes'
p3.yaxis.axis_label = 'Temps en secondes'
p3.line(dfD.index, dfD["Temps 50 000 simulations"],color='green')
p4 = figure(title="1 000, 10 000 et 50 000 simulations - Temps pour résoudre TSP")
p4.grid.grid_line_alpha=0.3
p4.xaxis.axis_label = 'Nombre de Villes'
p4.yaxis.axis_label = 'Temps en secondes'
p4.line(dfD.index, dfD["Temps 1 000 simulations"], color='red', legend='1 000 simulations')
p4.line(dfD.index, dfD["Temps 10 000 simulations"], color='blue', legend='10 000 simulations')
p4.line(dfD.index, dfD["Temps 50 000 simulations"], color='green', legend='50 000 simulations')
p4.legend.location = "top_left"
window_size = 30
window = np.ones(window_size)/float(window_size)
show(p1)
show(p2)
show(p3)
show(p4)
In [44]:
p5 = figure(title="1 000 simulations - Pourcentage d'écartement par rapport à TSP_Solver")
p5.grid.grid_line_alpha=0.3
p5.xaxis.axis_label = 'Nombre de Villes'
p5.yaxis.axis_label = 'Ecart en pourcentage'
p5.line(dfD.index, abs((dfD["Distance 1 000 simulations"]-dfD["Distance TSP_Solver"])/dfD["Distance TSP_Solver"]), color ="red")
p6 = figure(title="10 000 simulations - Pourcentage d'écartement par rapport à TSP_Solver")
p6.grid.grid_line_alpha=0.3
p6.xaxis.axis_label = 'Nombre de Villes'
p6.yaxis.axis_label = 'Ecart en pourcentage'
p6.line(dfD.index, abs((dfD["Distance 10 000 simulations"]-dfD["Distance TSP_Solver"])/dfD["Distance TSP_Solver"]), color ="blue")
p7 = figure(title="50 000 simulations - Pourcentage d'écartement par rapport à TSP_Solver")
p7.grid.grid_line_alpha=0.3
p7.xaxis.axis_label = 'Nombre de Villes'
p7.yaxis.axis_label = 'Ecart en pourcentage'
p7.line(dfD.index, abs((dfD["Distance 50 000 simulations"]-dfD["Distance TSP_Solver"])/dfD["Distance TSP_Solver"]), color ="green")
p8 = figure(title="1 000, 10 000 et 50 000 simulations - Pourcentage d'écartement par rapport à TSP_Solver")
p8.grid.grid_line_alpha=0.3
p8.xaxis.axis_label = 'Nombre de Villes'
p8.yaxis.axis_label = 'Ecart en pourcentage'
p8.line(dfD.index, abs((dfD["Distance 1 000 simulations"]-dfD["Distance TSP_Solver"])/dfD["Distance TSP_Solver"]),
color='red', legend='1 000 simulations')
p8.line(dfD.index, abs((dfD["Distance 10 000 simulations"]-dfD["Distance TSP_Solver"])/dfD["Distance TSP_Solver"]),
color='blue', legend='10 000 simulations')
p8.line(dfD.index, abs((dfD["Distance 50 000 simulations"]-dfD["Distance TSP_Solver"])/dfD["Distance TSP_Solver"]),
color='green', legend='50 000 simulations')
p8.legend.location = "top_left"
window_size = 400
window = np.ones(window_size)/float(window_size)
show(p5)
show(p6)
show(p7)
show(p8)
output_notebook()
Comparaison entre les méthodes:
In [45]:
p9 = figure(title="1 000 simulations - Les deux méthodes comparés")
p9.grid.grid_line_alpha=0.3
p9.xaxis.axis_label = 'Nombre de Villes'
p9.yaxis.axis_label = 'Temps en secondes'
p9.line(df.index[:28], df["Temps 1 000 simulations"] ,
color='red', legend='1 000 simulations Sans Dirichlet')
p9.line(df.index, dfD["Temps 1 000 simulations"] ,
color='blue', legend='1 000 simulations Avec Dirichlet')
p9.legend.location = "top_left"
p10=figure(title="10 000 simulations - Les deux méthodes comparés")
p10.grid.grid_line_alpha=0.3
p10.xaxis.axis_label = 'Nombre de Villes'
p10.yaxis.axis_label = 'Temps en secondes'
p10.line(df.index[:28], df["Temps 10 000 simulations"] ,
color='red', legend='10 000 simulations Sans Dirichlet')
p10.line(df.index, dfD["Temps 10 000 simulations"] ,
color='blue', legend='10 000 simulations Avec Dirichlet')
p10.legend.location = "top_left"
p11=figure(title="50 000 simulations - Les deux méthodes comparés")
p11.grid.grid_line_alpha=0.3
p11.xaxis.axis_label = 'Nombre de Villes'
p11.yaxis.axis_label = 'Temps en secondes'
p11.line(df.index[:28], df["Temps 50 000 simulations"] ,
color='red', legend='50 000 simulations Sans Dirichlet')
p11.line(df.index, dfD["Temps 50 000 simulations"] ,
color='blue', legend='50 000 simulations Avec Dirichlet')
p11.legend.location = "top_left"
window_size = 400
window = np.ones(window_size)/float(window_size)
show(p9)
show(p10)
show(p11)
output_notebook()
In [46]:
p8 = figure(title="1 000 simulations- Deux méthodes - Pourcentage d'écartement par rapport à TSP_Solver")
p8.grid.grid_line_alpha=0.3
p8.xaxis.axis_label = 'Nombre de Villes'
p8.yaxis.axis_label = 'Ecart en pourcentage'
p8.line(df.index[:28], abs((df["Distance 1 000 simulations"]-df["Distance TSP_Solver"])/df["Distance TSP_Solver"]),
color='red', legend='1 000 simulations Sans Dirichlet')
p8.line(df.index, abs((dfD["Distance 1 000 simulations"]-dfD["Distance TSP_Solver"])/dfD["Distance TSP_Solver"]),
color='blue', legend='1 000 simulations Avec Dirichlet')
p8.legend.location = "top_left"
p9 = figure(title="10 000 simulations - Deux méthodes - Pourcentage d'écartement par rapport à TSP_Solver")
p9.grid.grid_line_alpha=0.3
p9.xaxis.axis_label = 'Nombre de Villes'
p9.yaxis.axis_label = 'Ecart en pourcentage'
p9.line(df.index[:28], abs((df["Distance 10 000 simulations"]-df["Distance TSP_Solver"])/df["Distance TSP_Solver"]),
color='red', legend='10 000 simulations Sans Dirichlet')
p9.line(df.index, abs((dfD["Distance 10 000 simulations"]-dfD["Distance TSP_Solver"])/dfD["Distance TSP_Solver"]),
color='blue', legend='10 000 simulations Avec Dirichlet')
p9.legend.location = "top_left"
p10 = figure(title="50 000 simulations - Deux méthodes - Pourcentage d'écartement par rapport à TSP_Solver")
p10.grid.grid_line_alpha=0.3
p10.xaxis.axis_label = 'Nombre de Villes'
p10.yaxis.axis_label = 'Ecart en pourcentage'
p10.line(df.index[:28], abs((df["Distance 50 000 simulations"]-df["Distance TSP_Solver"])/df["Distance TSP_Solver"]),
color='red', legend='50 000 simulations Sans Dirichlet')
p10.line(df.index, abs((dfD["Distance 50 000 simulations"]-dfD["Distance TSP_Solver"])/dfD["Distance TSP_Solver"]),
color='blue', legend='50 000 simulations Avec Dirichlet')
p10.legend.location = "top_left"
window_size = 400
window = np.ones(window_size)/float(window_size)
show(p8)
show(p9)
show(p10)
output_notebook()
Changement par rapport au premier code envoyé¶
Test de 3 Ã 10 villes ! Avec 100 configurations des 100 villes, moyenne de distance, variance sans dirichlet, 10 000 simulations
In [59]:
l_etape = []
l=[]
for i in range(3,11):
for j in range(100):
villes = gen_villes(i)
S_tsp = tsp_solver(villes)
start_time = time.time()
S_etape = solution_traveling_salesman_problem_dirichlet(villes,10000)
timing_etape = time.time() - start_time
l_etape.append(S_etape[-2])
l_etape.append(timing_etape)
#l_etape.append(S_tsp[0])
l.append(l_etape)
l_etape=[]
In [64]:
dataf = pd.DataFrame(l, index = [i for i in range(3,11)])
dataf.index.names = ['Nombre de villes']
dataf
Out[64]:
In [88]:
dataf
distance = [i for i in range(0,200,2)]
time = [i+1 for i in range(0,200,2)]
In [94]:
dataf_time= dataf.drop(distance, axis=1)
dataf_distance = dataf.drop(time, axis=1)
dataf_time['Mean'] = dataf_time.mean(numeric_only=True, axis=1)
dataf_time['Std'] = dataf_time.std(numeric_only = True, axis=1)
dataf_distance['Mean'] = dataf_distance.mean(numeric_only=True, axis=1)
dataf_distance['Std'] = dataf_distance.std(numeric_only = True, axis=1)
dataf_distance
Out[94]:
In [102]:
from bokeh.plotting import figure, show, output_file
xs = dataf_time.index
yerrs = dataf_time["Std"]
ys = dataf_time["Mean"]
# plot the points
p = figure(title='Moyenne pour 100 simulations et intervalles de Deux Ecart-Types', width=800, height=400)
p.xaxis.axis_label = 'Nombres de Villes'
p.yaxis.axis_label = 'Moyenne de temps pour 100 villes'
p.line(dataf_time.index, ys,
color='blue', legend='Moyenne pour 100 simulations')
p.circle(xs, ys, color='blue', size=5, line_alpha=0)
p.legend.location = "top_left"
# create the coordinates for the errorbars
err_xs = []
err_ys = []
for x, y, yerr in zip(xs, ys, yerrs):
err_xs.append((x, x))
err_ys.append((y - 2*yerr, y + 2*yerr))
# plot them
p.multi_line(err_xs, err_ys, color='red')
show(p)
In [103]:
xs = dataf_distance.index
yerrs = dataf_distance["Std"]
ys = dataf_distance["Mean"]
# plot the points
p = figure(title='Moyenne pour 100 simulations et intervalles de Deux Ecart-Types', width=800, height=400)
p.xaxis.axis_label = 'Nombres de Villes'
p.yaxis.axis_label = 'Moyenne des distances pour 100 villes'
p.line(dataf_time.index, ys,
color='blue', legend='Moyenne pour 100 simulations')
p.circle(xs, ys, color='blue', size=5, line_alpha=0)
p.legend.location = "top_left"
# create the coordinates for the errorbars
err_xs = []
err_ys = []
for x, y, yerr in zip(xs, ys, yerrs):
err_xs.append((x, x))
err_ys.append((y - 2*yerr, y + 2*yerr))
# plot them
p.multi_line(err_xs, err_ys, color='red')
show(p)
Avec les villes du Tour de France¶
In [1]:
from geopy.geocoders import Nominatim
geolocator = Nominatim()
villes_étapes = ["Liège","Seraing-sur-Meuse","Visé","Tournai","Boulogne-sur-Mer","Abbeville","Rouen","Saint-Quentin",
"Epernay","Metz","Tomblaine","Belfort","Porrentruy","Besançon","Arc-et-Senans","Mâcon",
"Bellegarde-sur-Valserine","Albertville","La Toussuire","Saint-Jean-de-Maurienne","Annonay",
"Saint-Paul-Trois-Châteaux","Le Cap d'Agde","Limoux","Foix","Samatan","Pau","Bagnères-de-Luchon",
"Peyragudes","Blagnac","Brive-la-Gaillarde","Bonneval","Chartres","Rambouillet","Paris"]
Etapes = []
for ville in villes_étapes:
Etapes.append([ville,(geolocator.geocode(ville).latitude,geolocator.geocode(ville).longitude)])
print(Etapes)
Au cas où le module geopy n'est pas installé :
In [4]:
Etapes = [['Liège', (50.6451381, 5.5734203)], ['Seraing-sur-Meuse', (50.5966392, 5.5083375)], ['Visé', (50.7336644, 5.695536)], ['Tournai', (50.60566, 3.3878259)], ['Boulogne-sur-Mer', (50.7259985, 1.6118771)], ['Abbeville', (50.1060835, 1.8337029)], ['Rouen', (49.4404591, 1.0939658)], ['Saint-Quentin', (49.8486111, 3.2863888)], ['Epernay', (49.0436181, 3.9551593)], ['Metz', (49.1196964, 6.1763552)], ['Tomblaine', (48.6864409, 6.2106707)], ['Belfort', (47.6379599, 6.8628942)], ['Porrentruy', (47.4171297, 7.0761342)], ['Besançon', (47.237953, 6.0243246)], ['Arc-et-Senans', (47.0332329, 5.7818173)], ['Mâcon', (46.3036683, 4.8322266)], ['Bellegarde-sur-Valserine', (46.1085565, 5.8259295)], ['Albertville', (45.6754622, 6.3925417)], ['La Toussuire', (45.2557745, 6.2626689)], ['Saint-Jean-de-Maurienne', (45.2775258, 6.3453329)], ['Annonay', (45.2399639, 4.6675475)], ['Saint-Paul-Trois-Châteaux', (44.3475554, 4.7707325)], ["Le Cap d'Agde", (43.2845374, 3.5117752)], ['Limoux', (43.0538068, 2.2176533)], ['Foix', (42.9660039, 1.6096025)], ['Samatan', (43.4936111, 0.9316667)], ['Pau', (43.2957547, -0.3685667)], ['Bagnères-de-Luchon', (42.7910656, 0.5916857)], ['Peyragudes', (42.787583, 0.4766419)], ['Blagnac', (43.6434, 1.37799)], ['Brive-la-Gaillarde', (45.1584982, 1.5332389)], ['Bonneval', (45.3120931, 3.7409368)], ['Chartres', (48.4470039, 1.4866387)], ['Rambouillet', (48.6482463, 1.8328853)], ['Paris', (48.8566101, 2.3514992)]]
In [5]:
import matplotlib.pyplot as plt
In [6]:
from mpl_toolkits.basemap import Basemap
import numpy
import matplotlib.pyplot as plt
fig, axes = plt.subplots(1, 1, figsize=(9,9))
m = Basemap(llcrnrlon=-5, llcrnrlat=40, urcrnrlon=12, urcrnrlat=51,
resolution='i',projection='cass',lon_0=0,lat_0=0,
ax=axes)
m.drawcoastlines()
m.drawcountries()
m.fillcontinents(color='lightgrey', lake_color='#AAAAFF')
m.drawparallels(numpy.arange(-40,61.,2.))
m.drawmeridians(numpy.arange(-20.,21.,2.))
m.drawmapboundary(fill_color='#BBBBFF')
Etapes =[['Liège', (50.6451381, 5.5734203)], ['Seraing-sur-Meuse', (50.5966392, 5.5083375)], ['Visé', (50.7336644, 5.695536)], ['Tournai', (50.60566, 3.3878259)], ['Boulogne-sur-Mer', (50.7259985, 1.6118771)], ['Abbeville', (50.1060835, 1.8337029)], ['Rouen', (49.4404591, 1.0939658)], ['Saint-Quentin', (49.8486111, 3.2863888)], ['Epernay', (49.0436181, 3.9551593)], ['Metz', (49.1196964, 6.1763552)], ['Tomblaine', (48.6864409, 6.2106707)], ['Belfort', (47.6379599, 6.8628942)], ['Porrentruy', (47.4171297, 7.0761342)], ['Besançon', (47.237953, 6.0243246)], ['Arc-et-Senans', (47.0332329, 5.7818173)], ['Mâcon', (46.3036683, 4.8322266)], ['Bellegarde-sur-Valserine', (46.1085565, 5.8259295)], ['Albertville', (45.6754622, 6.3925417)], ['La Toussuire', (45.2557745, 6.2626689)], ['Saint-Jean-de-Maurienne', (45.2775258, 6.3453329)], ['Annonay', (45.2399639, 4.6675475)], ['Saint-Paul-Trois-Châteaux', (44.3475554, 4.7707325)], ["Le Cap d'Agde", (43.2845374, 3.5117752)], ['Limoux', (43.0538068, 2.2176533)], ['Foix', (42.9660039, 1.6096025)], ['Samatan', (43.4936111, 0.9316667)], ['Pau', (43.2957547, -0.3685667)], ['Bagnères-de-Luchon', (42.7910656, 0.5916857)], ['Peyragudes', (42.787583, 0.4766419)], ['Blagnac', (43.6434, 1.37799)], ['Brive-la-Gaillarde', (45.1584982, 1.5332389)], ['Bonneval', (45.3120931, 3.7409368)], ['Chartres', (48.4470039, 1.4866387)], ['Rambouillet', (48.6482463, 1.8328853)], ['Paris', (48.8566101, 2.3514992)]]
X = [Etapes[i][1][1] for i in range(len(Etapes))]
Y = [Etapes[i][1][0] for i in range(len(Etapes))]
N =[Etapes[i][0] for i in range(len(Etapes))]
for z,t,n in zip(X,Y,N):
lon = z
lat = t
x,y = m(lon, lat)
m.plot(x, y, 'bo', markersize=6)
plt.text(x, y,n, fontsize = 7)
plt.show()
On rajoute le trajet trouvé.
In [5]:
fig, axes = plt.subplots(1, 1, figsize=(9,9))
m = Basemap(llcrnrlon=-5, llcrnrlat=40, urcrnrlon=12, urcrnrlat=51,
resolution='i',projection='cass',lon_0=0,lat_0=0,
ax=axes)
m.drawcoastlines()
m.drawcountries()
m.fillcontinents(color='lightgrey', lake_color='#AAAAFF')
m.drawparallels(numpy.arange(-40,61.,2.))
m.drawmeridians(numpy.arange(-20.,21.,2.))
m.drawmapboundary(fill_color='#BBBBFF')
path = [4, 5, 6, 32, 33, 34, 8, 7, 3, 1, 0, 2, 9, 10, 12, 11, 13, 14, 16, 17, 19, 18, 15, 31, 20, 21, 22, 23, 24, 29, 25, 27, 28, 26, 30]
#Obtenu avec TSP_Solver
villes_sorted_pack = []
for i in range(len(path)):
villes_sorted_pack.append(Etapes[path[i]][1])
E = [villes_sorted_pack[i][1] for i in range(len(villes_sorted_pack))]
F = [villes_sorted_pack[i][0] for i in range(len(villes_sorted_pack))]
n=[villes_sorted_pack[i][0] for i in range(len(villes_sorted_pack))]
for z,t,n in zip(X,Y,N):
lon = z
lat = t
x,y = m(lon, lat)
m.plot(x, y, 'bo', markersize=6)
plt.text(x, y,n, fontsize = 7)
x, y = m(E, F)
m.plot(x, y, 'D-', markersize=10, linewidth=2, color='r', markerfacecolor='b')
plt.show()
